package algorithm.action;

import java.util.Stack;

public class StackPopOrder {

	public static void main(String[] args) {
		int[] pushA = {1,2,3,4,5};
		int[] popA = {4,5,3,2,1};
		int[] popB = {4,3,5,1,2};
		System.out.println(isPopOrder(pushA, popA));
		System.out.println(isPopOrder(pushA, popB));
	}
	
	static boolean isPopOrder(int[] pushA, int[] popA) {
		if(pushA == null || popA == null) return false;
		Stack<Integer> stack = new Stack<Integer>();
		int i = 0, j = 0;
		while(j < popA.length) {
			while(i < pushA.length && pushA[i] != popA[j]) {
				stack.push(pushA[i]);
				i++;
			}
			i++;
			j++;
			
			while(j < popA.length && !stack.isEmpty()) {
				int top = 0;
				if((top = stack.pop()) == popA[j]) {
					j++;
				} else {
					stack.push(top);
					break;
				}
			}
			if(i >= pushA.length && stack.isEmpty()) {
				return true;
			}
		}
		return false;
	}
}
